0% completed
Problem Statement
Given an array nums, containing N integers.
A 132 pattern consists of three numbers, say x, y, and z, where x < z and z < y. This is often referred to as a '132' pattern because if we represent x, y, and z as 1, 3, and 2, respectively, it mimics the positional pattern in '132'.
Return true if such a pattern exists within any sequence of given numbers nums. Otherwise, return false.
Examples
-
Example 1:
- Input: nums = [3, 5, 0, 3, 4]
- Expected Output: True
- Justification: Here, 3 < 4 and 4 < 5, forming a '132' pattern with the numbers 3, 5, and 4.
-
Example 2:
- Input: nums = [1, 2, 3, 4]
- Expected Output: False
- Justification: The sequence is in ascending order, and no '132' pattern is present.
-
Example 3:
- Input: nums = [9, 11, 8, 9, 10, 7, 9]
- Expected Output: True
- Justification: The pattern is formed with 8 < 9 and 9 < 10 in sequence 8, 10, 9.
Constraints:
n == nums.length- 1 <= n <= 2 * 105
- -109 <= nums[i] <= 109
Solution
The 132 Pattern problem requires finding a sequence of three numbers in an array such that the first number is smaller than the third number, which is in turn smaller than the second number. In other words, for indices i, j, and k, we need to find a pattern where nums[i] < nums[k] < nums[j] with i < j < k.
To solve this problem efficiently, we use a combination of a stack and a set to track potential candidates for the 132 pattern as we iterate through the array from the end to the beginning. This approach ensures that we can quickly identify and verify the necessary conditions for the pattern.
Step-by-Step Algorithm
-
Initialize Data Structures:
- Create a
SortedSetnamedsecondto store potential candidates for the second number in the 132 pattern. - Create a stack named
stto manage the numbers during the traversal.
- Create a
-
Iterate Through the Array from End to Beginning:
- Loop through the array from the last element to the first element (i.e., from right to left).
-
Manage the Stack:
- For each element
nums[i]in the array:- While the stack is not empty and the top element of the stack is smaller than
nums[i], pop the element from the stack and add it to thesecondset.
- While the stack is not empty and the top element of the stack is smaller than
- For each element
-
Check for the 132 Pattern:
- If the stack is not empty and the
secondset is not empty:- Iterate through the
secondset to find the smallest number that is greater thannums[i]. This is done using thehighermethod ofSortedSetwhich finds the smallest number in the set that is greater thannums[i]. - If such a number is found, it confirms the presence of the 132 pattern, and we return
True.
- Iterate through the
- If the stack is not empty and the
-
Push the Current Number onto the Stack:
- Push the current number
nums[i]onto the stack to potentially serve as the second number in future iterations.
- Push the current number
-
End of Iteration:
- If the loop completes without finding a 132 pattern, return
False.
- If the loop completes without finding a 132 pattern, return
Algorithm Walkthrough
Using the input nums = [9, 11, 8, 9, 10, 7, 9]:
-
Initialize Data Structures:
second = {}(empty set)st = [](empty stack)
-
Iteration from End to Beginning:
-
i = 6 (nums[i] = 9):
- Stack is empty.
- Push 9 onto the stack:
st = [9].
-
i = 5 (nums[i] = 7):
- Stack contains 9, which is greater than 7.
- Push 7 onto the stack:
st = [9, 7].
-
i = 4 (nums[i] = 10):
- Pop elements from the stack while they are smaller than 10:
- Pop 7, insert into
second:second = {7},st = [9]. - Pop 9, insert into
second:second = {7, 9},st = [].
- Pop 7, insert into
- Stack is empty.
- Push 10 onto the stack:
st = [10].
- Pop elements from the stack while they are smaller than 10:
-
i = 3 (nums[i] = 9):
- Stack contains 10, which is greater than 9.
- Check
secondfor an element greater than 9:second.upper_bound(9)finds 9, which is not greater than 9, so continue.
- Push 9 onto the stack:
st = [10, 9].
-
i = 2 (nums[i] = 8):
- Stack contains 9, which is greater than 8.
- Check
secondfor an element greater than 8:second.upper_bound(8)finds 9, which is greater than 8.- A
132pattern is found with 8 < 9 and 9 < 10.
- Return
True.
-
Code
Complexity Analysis
- Time Complexity: The time complexity is
due to the use of the SortedSetto find the higher bound, which takestime for each insertion and query. The overall complexity is since we iterate through the list once and perform log-time operations on the set. - Space Complexity: The space complexity is
for the stack and set, which can store up to (n) elements in the worst case.
Solution Using Stack
To solve this problem, we need to find a sequence of numbers in the array that follows the pattern 132. Specifically, we need to find indices i, j, and k such that i < j < k and nums[i] < nums[k] < nums[j].
We can achieve this by iterating backward through the array, using a stack to keep track of potential values for nums[k]. By maintaining a variable z to represent the largest value we have found that is smaller than the current number, we can efficiently check for the 132 pattern.
Step-by-Step Algorithm
-
Initialization:
- Initialize
ztoInteger.MIN_VALUEto represent the largest value smaller than the current number. - Create an empty stack to keep track of potential values for
nums[k].
- Initialize
-
Iterate Backward:
- Loop through the array
numsfrom the end to the beginning.
- Loop through the array
-
Check for Pattern:
- For each
nums[i], check if it is less thanz. If true, returnTruesince we have found a132pattern.
- For each
-
Update z and Stack:
- While the stack is not empty and the top of the stack is less than
nums[i], updatezto the top value of the stack and pop the stack. - Push the current
nums[i]onto the stack.
- While the stack is not empty and the top of the stack is less than
-
Return Result:
- If the loop completes without finding the pattern, return
False.
- If the loop completes without finding the pattern, return
Algorithm Walkthrough
Using the input: [9, 11, 8, 9, 10, 7, 9]
-
Initialization:
z = Integer.MIN_VALUEstack = []
-
Iterate Backward:
- Start from the last element and move to the first.
-
Iteration Details:
- Step 1:
nums[6] = 9- Stack is empty, push 9 onto the stack.
stack = [9]
- Step 2:
nums[5] = 7- 7 is not less than
z(which isInteger.MIN_VALUE). - Push 7 onto the stack.
stack = [9, 7]
- 7 is not less than
- Step 3:
nums[4] = 10- 10 is not less than
z. - While stack top is less than 10, update
zand pop from the stack.z = 7,stack = [9]z = 9,stack = []
- Push 10 onto the stack.
stack = [10]
- 10 is not less than
- Step 4:
nums[3] = 9- 9 is not less than
z(which is 9). - While stack top is less than 9, update
zand pop from the stack.z = 9,stack = [10]
- Push 9 onto the stack.
stack = [10, 9]
- 9 is not less than
- Step 5:
nums[2] = 8- 8 is less than
z(9). So, returntrue. .
- 8 is less than
- Step 1:
Code
Complexity Analysis
Time Complexity
- Building the stack: Each element is pushed onto the stack exactly once and can be popped from the stack at most once. Therefore, the operations of pushing and popping elements are
each. - Overall: Since we iterate through the array exactly once and perform
operations for each element (push and pop from the stack), the total time complexity is , where n is the number of elements in the array.
Space Complexity
- Stack Space: In the worst case, all elements are pushed onto the stack, leading to a stack space usage of
. - Variable Space: The additional space used by the variable
zis. - Overall: The overall space complexity is
, due to the space used by the stack.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Solution Using Stack
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity